package sword2offer;

public class Offer007 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return rebuild(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    public static TreeNode rebuild(int[] preorder,int [] inorder,int preLeft,int preRight,int inLeft,int inRight){
        if (preorder.length==0)return null;
        int root_val=preorder[preLeft];
        TreeNode root=new TreeNode(root_val);
        int index=0;
        for (int i = inLeft; i <=inRight ; i++) {
            if (inorder[i]==root_val){
                index=i;
                break;
            }
        }
        int leftLen=index-preLeft;
        int rightLen=inRight-index;
        if (leftLen>0)
        root.left=rebuild(preorder,inorder,preLeft+1,preLeft+leftLen,inLeft,index-1);
        if (rightLen>0)
        root.right=rebuild(preorder,inorder,preRight-rightLen+1,preRight,index+1,inRight);

        return root;
    }
}
